#include <iostream>
#include <fstream>
#include <limits>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <stack>

using namespace std;

class Vertex {
public:
	Vertex* pred;
	int G;
	int H;
	vector< vector<char> > state;

	Vertex() {
        G=0;
        H=0;
        pred=NULL;
		vector<char> subvector(4,0);
		vector< vector<char> > AM(4, subvector);
		state=AM;
	}
    
    Vertex(vector <vector<char> >& other_state) {
		state=other_state;
	}
    
    Vertex(const Vertex& other_vertex) {
        state=other_vertex.state;
	}

    void SetChildInfo() {
        SetH();
        G=pred->G+1;

    }
    
    long long GetHash() const {
         int p=19;
         long long hash=0;
         long long factor=1;
         for (size_t i=0; i<4; ++i) {
             for (size_t j=0; j<4; ++j) {
                 hash+=factor*(state[i][j]+1);
                 factor*=p;
             }
         }
         return hash;
    }

    void child_action(multimap<int, Vertex*>& mm, set<long long>& set_closed, Vertex*& child) {
        child->pred=this;
        child->SetChildInfo();
        
        if(set_closed.find(child->GetHash())==set_closed.end()) {
            mm.insert(make_pair(child->G+child->H, child));
        } else {
            delete child;
        }
    }

	void make_childs(multimap<int, Vertex*>& mm, set<long long>& set_closed) {
        char zero_i, zero_j;

		for (size_t i=0; i<4;++i)
			for (size_t j=0; j<4; ++j)
				if(state[i][j]==0) {
					zero_i=i;
					zero_j=j;
				}

		if(zero_i!=3) {
			Vertex* child1 = new Vertex(*this);
			child1->state[zero_i][zero_j]=child1->state[zero_i+1][zero_j];
			child1->state[zero_i+1][zero_j]=0;
            child_action(mm, set_closed, child1);
		}

		if(zero_i!=0) {
			Vertex* child2 = new Vertex(*this);
			child2->state[zero_i][zero_j]=child2->state[zero_i-1][zero_j];
			child2->state[zero_i-1][zero_j]=0;
            child_action(mm, set_closed, child2);
		}

		if(zero_j!=3) {
			Vertex* child3 = new Vertex(*this);
			child3->state[zero_i][zero_j]=child3->state[zero_i][zero_j+1];
			child3->state[zero_i][zero_j+1]=0;
            child_action(mm, set_closed, child3);
		}

		if(zero_j!=0) {
            Vertex* child4 = new Vertex(*this);
			child4->state[zero_i][zero_j]=child4->state[zero_i][zero_j-1];
			child4->state[zero_i][zero_j-1]=0;
            child_action(mm, set_closed, child4);
		}

	}

	int print() {
		for (size_t i=0; i<4;++i) {
			for (size_t j=0; j<4; ++j) {
				cout<<(short)state[i][j]<<"\t";
			}
			cout<<"\n";
		}

		cout<<"\n";
		return 0;
	}

	int scan(){
		for (size_t i=0; i<4;++i) {
			for (size_t j=0; j<4; ++j) {
                short tmp;
                cin>>tmp;
				state[i][j]=tmp;
			}
		}

		return 0;
	}
private:
    int SetH() {
		int final_H=0;
		for (char i=0; i<4;++i)
			for (char j=0; j<4; ++j) {
				if(state[i][j]!=0) {
					int current_number=state[i][j]-1;
					int a=abs(j-current_number%4);
					int b=abs(i-(current_number/4));
					final_H+=a+b;
				}
			}

        //and now check Linear conflict
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 3; ++j)
                for (int k = j + 1; k < 4; ++k)
                    if (state[i][j] > state[i][k] && state[i][j] > i * 4 && state[i][j] <= (i + 1) * 4 && state[i][k] > i * 4 && state[i][k] <= (i + 1) * 4)
                        final_H += 2;
            
            for (int j = 0; j < 4 - 1; ++j)
                for (int k = j + 1; k < 4; ++k)
                    if (state[j][i] > state[k][i] && state[j][i] % 4 == i + 1 && state[k][i] % 4 == i + 1)
                        final_H += 2;
        }

        if (state[0][2] == 3 && state[1][3] == 8 && state[0][3] != 4)
            if (state[0][3] != 1 && state[0][3] != 2 && state[0][3] != 12 && state[0][3] != 0)
                final_H += 2;
        if (state[2][0] == 9 && state[3][1] == 14 && state[3][0] != 13)
            if (state[3][0] != 1 && state[3][0] != 5 && state[3][0] != 15 && state[3][0] != 0)
                final_H += 2;
        if (state[0][1] == 2 && state[1][0] == 5 && state[0][0] != 1)
            if (state[0][0] != 3 && state[0][0] != 4 && state[0][0] != 9 && state[0][0] != 13)
                final_H += 2;
        
        final_H += 4;
        for (size_t i = 0; i < 4; ++i) {
            if (state[3][i] == 15) { final_H -= 2; }
            if (state[i][3] == 12) { final_H -= 2; }
        }

        H=final_H;
		return final_H;
	}
};

int IsSolution(Vertex*& V1) {
    int N=0;
    for (size_t i=0; i<4; ++i) {
        for (size_t j=0; j<4; ++j) {
            if(V1->state[i][j]==0) N+=i+1;

            for (size_t n=j; n<4; ++n) if(V1->state[i][n]<V1->state[i][j] && V1->state[i][n]!=0) {
                ++N;
            }

            for (size_t n=i+1; n<4; ++n) {
                for (size_t t=0; t<4; ++t) {
                    if(V1->state[n][t]<V1->state[i][j] && V1->state[n][t]!=0) {
                        ++N;
                    }
                }
            }
        }
    }
    //cout<<N<<endl;
    if (N%2!=0) return 0; else return 1;
}


int PrintSolutionStates(Vertex*& V1, Vertex*& CurV) {
    Vertex* V=CurV->pred;
    stack<Vertex*> pass;

    do {
        pass.push(V);
        V=V->pred;
    } while (V->GetHash()!=V1->GetHash());

    while(!pass.empty()) {
        pass.top()->print();
        cout<<endl;
        pass.pop();
    }

    CurV->print();
    return 0;
}

int AStar(multimap<int, Vertex*>& mm, set<long long>& set_closed, Vertex*& V1) {
	vector<char> subvector(4,0);
	vector< vector<char> > idealState(4, subvector);

    for (size_t i=0; i<4; ++i)
        for (size_t j=0; j<4; ++j)
            idealState[i][j]=i*4+j+1;

    idealState[3][3]=0;

    mm.insert(make_pair(0, V1));
    cout<<"Start state:"<<endl;
    V1->print();


    while(!mm.empty()) {
        Vertex* CurV=mm.begin()->second;
        if(CurV->state==idealState) {
            cout<<"It's possible for "<<CurV->G<<" stages:"<<endl<<endl;
            PrintSolutionStates(V1, CurV);
            return 0;
        }
        mm.erase(mm.begin());
        if(set_closed.find(CurV->GetHash())==set_closed.end()) {
            set_closed.insert(CurV->GetHash());
            CurV->make_childs(mm, set_closed);
        }
    }

    return 1;
}

int main(){
    
    if(freopen("in.txt", "r", stdin)==NULL) {
        cout<<"Error: input file can't be opened";
        return 1;
    }
    if(freopen("out.txt", "w", stdout)==NULL) {
        cout<<"Error: output file can't be opened";
        return 1;
    }

    multimap<int, Vertex*> mm;
    set<long long> set_closed;

    //Scan start state
    Vertex* V1=new Vertex();
    V1->scan();

    //Chek if there is any decisions
    if(!IsSolution(V1)) {
        cout<<"No solution."<<endl;
        //system("pause");
        return 0;
    }

    //Start A-star algorithm
    if(AStar(mm, set_closed, V1)!=0) cout<<"No solution!"<<endl;

    //system("pause");

	return 0;
}